C_Cpp

STL源码剖析_迭代器

文章目录
  1. 1. 何为迭代器
  2. 2. 实现一个简单的迭代器
  3. 3. 参考

按照《STL源码剖析》中STL知识的编排顺序，学习完空间配置器之后，就是迭代器和traits编程技法了，学习完这三个概念，才算做好了继续学习stl的准备。

何为迭代器

《设计模式》中对iterator是这样定义的：提供一种方法，使之能够依序巡防某个容器所含的各个元素，而又无需暴露该容器的内部表述方式。
在STL中，数据容器和算法是分开的，所以就需要迭代器这种胶合剂来给算法提供一个访问不同容器的的途径，这样只需要一套算法，就能访问不同的容器。
迭代器的使用方法和行为非常像一个指针，也有取值(dereference或*操作)、取址、->、++、–、==、!=等操作。所以迭代器也可以看作一个智能指针。

实现一个简单的迭代器

由于迭代器给算法提供了一个访问容器的途径，当前存在下面这样一个算法:

1
2
3
4
5
6
7
template <typename InputIterator,typename T>
InputIterator find(InputIterator first,InputIterator last,const T&value){
    while(first != last && *first!=value){
        ++first;
    }
    return first;
};

然后自己编写了一个容器，想要使用这个算法，就得给自己的容器编写对应的迭代器。以下代码实现了一个简单的list链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//list.h
\#ifndef ITERATORTEST_LIST_H
\#define ITERATORTEST_LIST_H

#include <iostream>

template <typename T>
class ListItem{
public:
    T value() const {
        return _value;
    }
    ListItem* next() const {
        return _next;
    }
public:
    T _value;
    ListItem *_next;
};

template <typename T>
class List{
public:
    List();
    void pushfront(T value);
    void pushback(T value);
    void display();
    ListItem<T>* front();
    ~List();
private:
    ListItem<T> *_front;
    ListItem<T> *_end;
    long _size;
};


template <typename T>
List<T>::List() {
    _front=nullptr;
    _end=nullptr;
    _size=0;
}

template <typename T>
void List<T>::pushfront(T value) {
    ListItem<T> *temp=new ListItem<T>();
    temp->_value=value;
    if(_size==0){
        _front=temp;
        _end=temp;
    }else{
        temp->_next=_front;
        _front=temp;
    }
    _size++;
}

template <typename T>
void List<T>::pushback(T value) {
    ListItem<T> *temp=new ListItem<T>();
    temp->_value=value; temp->_next=nullptr;
    if(_size==0){
        _front=temp;
    }else{
        _end->_next=temp;
    }
    _end=temp;
    _size++;
}

template <typename T>
void List<T>::display(){
    ListItem<T> *cur=_front;
    while(cur->_next!=nullptr){
        std::cout<<cur->_value<<" ";
        cur=cur->_next;
    }
    std::cout<<cur->_value<<" ";
}

template <typename T>
ListItem<T>* List<T>::front(){
    return _front;
}

template <typename T>
List<T>::~List(){
    ListItem<T> *cur=_front;
    ListItem<T> *t=_front;
    while(cur!=nullptr){
        t=cur->_next;
        delete cur;
        cur=t;
    }
}

\#endif //ITERATORTEST_LIST_H

然后为该list实现一个迭代器，其中主要是对各个运算符的重载：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//listiter.h
#ifndef ITERATORTEST_LISTITER_H
#define ITERATORTEST_LISTITER_H

#include <iostream>

//因为find中需要使用!=来判断ListItem<T>类型和T类型是否相等，原有的!=运算符无法进行比较，所以需要自己重载这个运算符。
template <typename T>
bool operator!=(const ListItem<T>& item,T n){
    return item.value() !=n;
}

template <typename Item>
class ListIter{
public:
    ListIter(Item *p=0):ptr(p){}
    Item& operator*() const {
        return *ptr;
    }
    Item* operator->() const{
        return ptr;
    }
    //前置运算符
    ListIter& operator++(){
        ptr=ptr->next();
        return *this;
    }
    //后置运算符
    ListIter& operator++(int){
        ListIter tmp=*this;
        ++*this;
        return tmp;
    }
    bool operator==(const ListIter& i) const{
        return ptr==i.ptr;
    }
    bool operator!=(const ListIter& i) const{
        return ptr!=i.ptr;
    }

private:
    Item *ptr;
};

#endif //ITERATORTEST_LISTITER_H

最后main.cpp测试代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include "list.h"
#include "listiter.h"

template <typename InputIterator,typename T>
InputIterator find(InputIterator first,InputIterator last,const T&value){
    while(first != last && *first!=value){
        ++first;
    }
    return first;
};


int main() {
    List<int> l;
    l.pushback(1);
    l.pushback(2);
    l.pushback(3);
    l.pushback(4);
    l.pushback(5);
    l.pushback(6);
    l.display();
    std::cout<<std::endl;

    //使用find()
    ListIter<ListItem<int> > begin(l.front());
    ListIter<ListItem<int> > end;
    ListIter<ListItem<int> > iter;
    iter=find(begin,end,4);
    if(iter!=end){
        std::cout<<"found! "<<iter->value()<<std::endl;
    }else{
        std::cout<<"not found. "<<std::endl;
    }

    return 0;
}

参考

  • 《STL源码剖析》

欢迎与我分享你的看法。
转载请注明出处：http://taowusheng.cn/

Powered By Valine
v1.5.2